# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e


class Interval(object):
    def __init__(self, s=0, e=0):
        self.start = s
        self.end = e


class Solution(object):



    def merge(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: List[Interval]
        """
        if len(intervals) == 0:
            return intervals

        def comp(x, y):
            if x.start < y.start:
                return -1
            elif x.start > y.start:
                return 1
            else:
                if x.end < y.end:
                    return -1
                elif x.end > y.end:
                    return 1
                else :
                    return 0
        intervals = sorted(intervals, comp)
        pre = intervals[0]
        remove = []
        for i in range(1, len(intervals)):
            now = intervals[i]
            if pre.end >= now.start:
                now.start = pre.start
                now.end = max(now.end, pre.end)
                remove.append(pre)
            pre = now
        for i in remove:
            intervals.remove(i)
        return intervals


    def merge1(self, intervals):
        out = []
        for i in sorted(intervals, key=lambda i: i.start):
            if out and i.start <= out[-1].end:
                out[-1].end = max(out[-1].end, i.end)
            else:
                out += i,
        return out


test = Solution()
i1 = Interval(2,3)
i2 = Interval(2,2)
i3 = Interval(3,3)
i4 = Interval(1,3)
i5 = Interval(5,7)
i6 = Interval(2,2)
i7 = Interval(4,6)
l =[i1,i2,i3,i4,i5,i6,i7]
test.merge(l)

